Мiнiстерство освiти і науки, молоді та спорту України Національний університет «Львівська політехніка» Кафедра ЕОМ Курсова робота з дисципліни «Програмування. Частина ІІІ.Структури даних та алгоритми» Завдання 2: Динамічні структури даних № = (8+4+75)%3+1= 1 № = (8+75)%10+1= 4  Львів – 2011 Зміст 2. Завдання 2: Динамічні структури даних………………………………………….... 3 2.1. Теоретична частина………………………………………………………… 3 2.2. Частина 1. Побудова АТД………………………………………………….6 2.2.1. Постановка задачі……………………………………………………6 2.2.2. Динаміка вмісту……………………………………………………...6 2.2.3. Результати виконання програми……………………………………7 2.3. Частина 2. Застосування АТД…………………………………………….8 2.3.1. Постановка задачі……………………………………………………8 2.3.2. Алгоритм розв’язання задачі………………………………………..8 2.3.3. Результати виконання програми……………………………………11 Висновки………………………………………………………………………… 12 Список літератури………………………………………………………………13 Додатки………………………………………………………………………… 14  Завдання №2. Динамічні структури даних 2.1 Теоретична частина Стек - динамічна структура даних, що являє собою впорядкований набір елементів, в якій додавання нових елементів і видалення існуючих виробляється з одного кінця, званого вершиною стека. За визначення, елементи витягуються з стека в порядку, зворотному їх додаванню в цю структуру, тобто діє принцип "останній прийшов - перший пішов "(LIFO – Last In, First Out). Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання і зняття кілець здійснюється саме згідно з визначенням стека. Стек можна організувати на базі будь-якої структури даних, де можна зберігати кількох однотипних елементів і де можна реалізувати визначення стека: лінійний масив, типізований файл, односпрямований або двонаправлений список. У нашому випадку найбільш відповідним для реалізації стека є односпрямований список, причому як вершини стека виберемо початок цього списку. Виділимо типові операції над стеком і його елементами: додавання елемента в стек; видалення елемента з стека; перевірка, чи порожній стек; перегляд елемента в вершині стека без видалення; очищення стека. Для формування стека і роботи з ним необхідно мати дві змінні типу покажчик, перша з яких визначає вершину стека, а друга - допоміжна. Операції зі стеком Виконання операції push push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow) pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow) Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку. Додаткові операції (присутні не у всіх реалізаціях стеку): isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній. isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе. clear: звільнити стек (видалити усі елементи). top: отримати верхній елемент (без виштовхування). size: отримати розмір (кількість елементів) стека. swap: поміняти два верхніх елементи місцями. Організація в пам'яті комп'ютера Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку. Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах а...